CF1324F Maximum White Subtree
题意
给定一棵 个结点的树,每个点的颜色是黑白中的一种。对于每个结点 ,选出一棵包含点 的连通子树,求其中白点数减去黑点数的最大值。
Nothing with me, but Forever.
给定一棵 n 个结点的树,每个点的颜色是黑白中的一种。对于每个结点 u,选出一棵包含点 u 的连通子树,求其中白点数减去黑点数的最大值。
考虑在一个二维平面上,x 轴表示在一条直线上大楼排列的坐标,y 轴表示大楼的高度,那么第 i 栋大楼可以用 (i,hi) 表示。如果第 i 栋大楼与第 j 栋大楼满足 i<j 且 ihi≥jhj,那么第 j 栋大楼被第 i 栋大楼挡住而不可视见。求从 (0,0) 最多能看到的大楼数量。
悬线法裸题。
从 1 到 n 每个位置有一个高度为 hi,宽度为 1 的矩形。
求所有矩形覆盖面积中最大子矩形。
给定 n 个数分别有 2 个权值 ai,bi,选取一些数使得 ∑ai≥0,∑bi≥0 的条件下求 ∑ai+bi 的最大值。
存在依赖关系背包转化分组背包。
给定 n 个物品的价值和体积,他们之间存在简单的依赖关系,即一个结点要么是父亲结点,要么是儿子结点,且一个父亲结点最多有两个儿子结点。
考虑现在有 n 本书并给定一个最大长度 L,第 i 本书有高度 hi,wi。每次选取一段范围满足该段范围内的所有书的 ∑wi≤L,那么这次选取的贡献为 max{hi}。